Satellite navigation systems are becoming increasingly important in a wide range of applications, including handheld devices for position determination, in-car navigation support, and so on. The main satellite navigation system in service at present is the global positioning system (GPS) operated by the United States Department of Defense. Worldwide sales of GPS equipment reached nearly 3.5 billion dollars in 2003, and this figure is expected to grow steadily over the next few years. A European counterpart satellite navigation system, named Galileo, is planned for launch and service availability later this decade.
A satellite navigation system comprises a constellation of satellites, each of which broadcasts one or more signals to earth. The basic components of a satellite signal are a spreading code (also referred to as a positioning, synchronisation or ranging code) which is combined with navigation data. The resulting combination is then modulated onto a carrier at a set frequency for transmission to earth. Each satellite generally transmits at multiple frequencies, which can help to compensate for ionospheric effects, to improve accuracy and to broadcast more data.
In some cases, multiple channels may be modulated onto a single carrier via some appropriate multiplexing scheme. For example, it is planned for certain Galileo signals to comprise a data channel combined with a pilot channel. The pilot channel contains only a spreading code, but no navigation data, while the data channel contains both the spreading code and the navigation data.
The spreading code component of a satellite signal typically comprises a predetermined sequence of bits (referred to as ‘chips’) and is used to perform two main tasks. Firstly, the spreading code provides a synchronisation and access (CDMA) mechanism to allow a receiver to lock onto a satellite signal. Thus each satellite (and typically each signal broadcast from that satellite) has its own synchronisation code. When a receiver is first switched on, it does not know which satellite signals can be received, since certain satellites in the constellation will be below the horizon for that particular location at that particular time. The receiver uses the synchronisation codes to lock onto a signal from a first satellite. Once this has been done, the navigation data in the signal can be accessed. This then provides almanac data for the other satellites in the constellation, and allows the remaining satellites that are visible to the receiver to be acquired relatively quickly.
Many receivers employ a two-phase acquisition process. In the first phase, the receiver performs a simultaneous correlation of the incoming signal against the set of satellite spreading codes. In particular, the receiver searches for a spreading code from any satellite, allowing for any possible timing offset between the satellite and the receiver, and for any possible Doppler shift between the satellite and the receiver (which is dependent on the motion of the satellite in space relative to the user). If a correlation value is found to exceed a predetermined threshold, then a second phase involving a more detailed analysis is performed for the relevant combination of satellite spreading code, timing offset and Doppler shift. This second-phase analysis verifies and confirms or if necessary rejects the initial coarse acquisition.
The second main task of a spreading code is to provide a distance estimate from the satellite to the receiver, based on the time that it has taken the signal to travel from the satellite to the receiver. The position of the receiver is then determined in three-dimensional space by using a process of trilateration, given the known positions of the satellites (as specified in the navigation data received from the satellites). In theory, trilateration can be performed with signal information from a minimum of three satellites, assuming that the timing offset between the receiver clock and satellite clocks is known. In practice, this timing offset is generally unknown, except for specialised receivers, so that signal information is obtained from at least one additional satellite to compensate for the unknown time offset at the receiver. If signals from further satellites are available, a statistical position determination can be performed using any appropriate algorithm such as least squares. This can also provide some indication of the error associated with an estimated position.
One important parameter for a spreading code is the chip rate at which the spreading code is transmitted, since this in turn controls the accuracy with which the positional determination can be made. Another important parameter for a spreading code is its total length, in other words the number of chips in the spreading code before it repeats. One reason for this is that the finite length of a spreading code can lead to ambiguity in the position determination. A longer length for the spreading code reduces such ambiguity, and also provides better separation of signals from different sources and increased robustness against interference. On the other hand, having a longer repetition length for the spreading code may delay initial acquisition of the signal, as well as requiring more processing capability within the receiver. In general, the length of the spreading code also impacts the data rate that can be used for the navigation data, since there is normally only one bit of navigation data for each complete spreading code sequence. Therefore, the longer the repetition length for the spreading code, the lower the bit rate for the navigation data.
One known strategy is to use a hierarchical or tiered spreading code based on primary and secondary codes. If we assume that a primary code has N1 chips and a secondary code has N2 chips, then the first N1 chips of the overall spreading code correspond to the primary sequence exclusive-ORed with the first chip of the secondary code, the next N1 chips of the spreading code comprise a repeat of the N1 chips of the primary code, this time exclusive-ORed with the second chip of the secondary code, and so on. This gives a total repetition length for the code of N1×N2, however the initial acquisition can be based on the primary code only.
The GPS spreading codes are implemented using linear feedback shift registers (LFSRs), in which selected outputs from an N-stage shift register are tapped and fed back to the input. The feedback connections within the LFSR can be represented as a binary polynomial in modulo-2 arithmetic of order N, whereby the operation of an LFSR is fully specified by its polynomial and the initial setting of the LFSR.
The GPS spreading codes are Gold codes, which have certain special mathematical properties. One of these is that they generate an output of pseudo-random noise (PRN) having a repetition length of 2N−1, so that a relatively compact LFSR can generate an output with a long repetition length. Gold codes also have good auto-correlation properties that support code acquisition and accurate positioning. In particular, the autocorrelation function has a well-defined peak at zero time shift, and is relatively small for all other (i.e. non-zero) time shifts. At the same time it is also important to select a set of Gold codes that has good cross-correlation properties, whereby the cross-correlation function between different codes is relatively small. This is important for signal acquisition, since it helps to prevent a synchronisation code from one satellite being accidentally mistaken for a synchronisation code from another satellite. A further important practical criterion for a spreading code is to have equal (or nearly equal) numbers of ones and zeros—this is referred to as balancing.
Additional information about satellite navigation systems can be found in: “Global Positioning System: Signals, Measurements and Performance”, by Misra and Enge, Ganga-Jamuna Press, 2001, ISBN 0-9709544-0-9; “Global Positioning System: Theory and Applications”, Vol 1 and Vol 2, by Bradford W. Parkinson and James J. Spilker Jr, ISBN 1-56347-106-X, published by the American Institute for Aeronautics and Astronautics; “Galileo User Segment Overview” by Hollreiser et al, ION GPS/GNSS 2003, September 2003, Portland, Oreg., p1914-1928; and “Galileo Test User Segment—First Achievements and Application”, by Hollreiser et al, GPS World, July 2005.
Although the use of Gold codes is well-established for existing satellite navigation systems, there are some limitations associated with such codes. For example, they are only available with certain code lengths (2N−1, and not all values of N can be used for the LFSR polynomial). In general, the code length is determined by the ratio of the chip rate of the spreading code and the bit rate of the navigation data. If the code length is restricted to an available Gold code, then this implies a constraint on the chip rate and the bit rate, which might in turn impact other considerations, such as acquisition time and positioning accuracy. In some cases, the limitation on code length for Gold codes has been overcome by using truncated Gold codes, but this truncation has an adverse impact on the mathematical properties of the code set (in terms of the autocorrelation function, etc).
Accordingly, it has been proposed in PCT applications PCT/EP2004/014488 and PCT/EP2005/007235 to use custom-designed or bespoke bit sequences as satellite spreading codes. This allows the development of spreading codes of arbitrary length, and also permits the optimisation of various properties such as auto-correlation and cross-correlation independent from other constraints. Such a spreading code will be described herein as a “memory” code, since in general a receiver stores the entire chip pattern of the code. This is in contrast to generating the chip pattern algorithmically, as for a Gold code, which uses a LFSR to generate a code algorithmically in accordance with its polynomial, rather than storing the chip pattern of the whole code. Note that since memory codes are typically created from (pseudo) random number sequences, they are not normally amenable to data compression techniques.
The set of memory codes for a receiver can be stored within some form of ROM such as flash memory. These codes can then be loaded into the receiver chipset at boot time for use during detection of the spreading codes in the incoming satellite signals. If the complete memory codes are loaded into the receiver chipset itself, this may represent a very significant overhead in terms of storage locations on the receiver chipset. Alternatively, the codes might be loaded into a RAM (external to the receiver chipset), where they would represent only a comparatively small addition to the overall program and/or data storage requirements for general receiver operations. However, in this case a dedicated high-speed interface to feed the codes in real-time from the RAM onto the receiver chipset is likely to be required, as well as some additional internal buffering within the receiver chipset itself.
FIG. 1 depicts a typical implementation of an LFSR, as might for example be provided within a conventional GPS receiver chipset. The basic hardware includes a shift register 11 of length N, plus two additional registers 12, 13, each also of length N. The design of the shift register itself is generic, in that the feedback taps are not hard-wired. Rather, feedback between the various stages of the shift register 11 is controlled by the polynomial value that is loaded into one of the two additional registers (the polynomial register 12). The initial setting of the LFSR is then determined by the value stored in the other additional register (the initial pattern register 13). In this way, the LFSR of FIG. 1 can be customised by providing appropriate values into the polynomial register and the initial pattern register.
The LFSR of FIG. 1 comprises 3N storage locations (since the shift register 11, the polynomial register 12, and the initial pattern register 13 each has N storage locations). As noted above, for a maximal Gold code the number of storage locations in the feedback shift register 11 is related to the length of the output code (L) by N=2 log(L+1). Since a Gold code is generally based on combining the outputs from 2 LFSRs, the total number of storage locations T(S) for a Gold code can be expressed as: T(S)=6*2 log(L+1). In addition, a standard LFSR code generator has some combinatorial logic to provide the feedback taps (XORs), as well as a small state-machine/controller in combination with a counter (or comparator+register) for resetting, reloading and restarting at the end of the sequence.
In contrast, a straightforward implementation of a memory code in a receiver might involve providing a full-length memory for each code to be stored in the receiver, including the relevant address decoders. The memory can be static or dynamic, depending on the implementation technology chosen. Most wide spread technologies (ASIC, FPGAs) support static memories. In addition, a small state-machine or controller for address generation would typically be used to ensure reading of the correct memory cell. Assuming that the equivalent gate-count of a static memory cell is 1.5 NAND2 (NAND2 represents a two-input NAND gate and typically comprises 6 transistors), then for 0.18 μm technology this results in an area of 18.75 μm2 per memory cell. Including 200 gates for the state-machine/controller, and assuming a 4096 chip code (corresponding to the Galileo L1 signal), this is equivalent to 6344 NAND2 gates, with an overall area of 79300 μm2. Alternatively, for a 10230 chip code, as for the Galileo E5a signal, and based on the same assumptions as above, this is equivalent to 15545 NAND2 gates, with an overall area of 194312 μm2 (neglecting any savings due to the regularity of the structure). This can represent a significant overhead for the receiver chipset.
Note also that for the memory code case, T(S)≈L. In other words, the number of storage locations rises in direct proportion to the length of the code, rather than in proportion to the logarithm of the code, as for an LFSR implementation. It is clear therefore that as the length of the spreading code increases, the use of memory codes demands significantly more storage locations than a conventional LFSR approach. This problem is exacerbated, in that a receiver has to store not one spreading code, but rather the complete set of spreading codes for all satellites and for all signals of interest.